class Permutation {
public:
    vector<string> getPermutation(string str) {
        // write code here
        vector<string> all;
        if(str.size() == 0){
            return all;
        }
        string tmp;
        for(int i=0;i<str.size();i++){
            for(int j=str.size();j>i;j--){
                if(str[j]>str[j-1]){
                    char t = str[j];
                    str[j] = str[j-1];
                    str[j-1] =t;
                }
            }
        }
        recur(str, tmp, all, 0);
        return all;
    }
    void recur(string str, string& tmp, vector<string> &all, int start){
        if(start < 0 || str.size() == 0){
            return;
        }
        if(str.size() == start){
            all.push_back(tmp);
            return;
        }
        for(int i = start; i < str.size(); i++){
            if(i != start && str[i] == str[start]){    //如果字符相同，不用交换
                continue;
            }
            swap(str[i], str[start]);
            tmp +=  str[start];
            recur(str, tmp, all, start + 1);
            tmp.pop_back();            //回溯法的关键
        }
    }
};